<!DOCTYPE html>
<html lang="en">
    <head prefix="og: https://ogp.me/ns#">
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <meta name="color-scheme" content="light dark">
  
  <title>数组 - Satellite</title>
  
    <link rel="shortcut icon" href="/favicon.png">
  
  
    <link rel='manifest' href='/manifest.json'>
  

  
  
  
  <meta property="og:title" content="数组 - Satellite" />
  
  <meta property="og:type" content="article" />
  
  <meta property="og:url" content="http://example.com/2023/09/21/%E6%95%B0%E7%BB%84/index.html" />
  
  <meta property="og:image" content="/favicon.png" />
  
  <meta property="og:article:published_time" content="2023-09-21T02:05:54.000Z" />
  
  <meta property="og:article:author" content="John Doe" />
  
  

  
<link rel="stylesheet" href="/css/var.css">

  
<link rel="stylesheet" href="/css/main.css">

  
<link rel="stylesheet" href="/css/typography.css">

  
<link rel="stylesheet" href="/css/code-highlighting.css">

  
<link rel="stylesheet" href="/css/components.css">

  
<link rel="stylesheet" href="/css/nav.css">

  
<link rel="stylesheet" href="/css/paginator.css">

  
<link rel="stylesheet" href="/css/footer.css">

  
<link rel="stylesheet" href="/css/post-list.css">

  
  
<link rel="stylesheet" href="/css/rainbow-banner.css">

  
  
  
<link rel="stylesheet" href="/css/toc.css">

  
  
  
  
  
<link rel="stylesheet" href="/css/post.css">

  
  
  
  
  

  
<meta name="generator" content="Hexo 6.3.0"></head>
    <body
        data-color-scheme="auto"
        data-uppercase-categories="true"
        
        data-rainbow-banner="true"
        data-rainbow-banner-shown="auto"
        data-rainbow-banner-month="6"
        data-rainbow-banner-colors="#e50000,#ff8d00,#ffee00,#008121,#004cff,#760188"
        
        data-config-root="/"
        
        data-toc="true"
        data-toc-max-depth="2"
        
        
    >
        <nav id="theme-nav">
    <div class="inner">
        <a class="title" href="/">Satellite&#39;s Blog</a>
        <div class="nav-arrow"></div>
        <div class="nav-items">
            <a class="nav-item nav-item-home" href="/">Home</a>
            
            
            <a class="nav-item" href="/archives">Archives</a>
            
            
            
            <a class="nav-item" href="/about">About</a>
            
            
            
            <a class="nav-item nav-item-github nav-item-icon" href="https://github.com/Satellite2426" target="_blank" aria-label="GitHub">&nbsp;</a>
            
            
        </div>
    </div>
</nav>
        
<article class="post">
    <div class="meta">
        

        
        <div class="date" id="date">
            <span>September</span>
            <span>21,</span>
            <span>2023</span>
        </div>
        

        <h2 class="title">数组</h2>
    </div>

    <div class="divider"></div>

    <div class="content">
        <h1 id="1-数组"><a href="#1-数组" class="headerlink" title="1. 数组"></a>1. 数组</h1><h2 id="1-1-定义"><a href="#1-1-定义" class="headerlink" title="1.1 定义"></a>1.1 定义</h2><p>在计算机科学中，数组是由一组元素(值或变量)组成的数据结构，每个元素有至少一个索引或键来标识</p>
<blockquote>
<p>In computer science, an <strong>array</strong> is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key</p>
</blockquote>
<p>因为数组内的元素是<strong>连续存储</strong>的，所以数组中元素的地址，可以通过其索引计算出来，例如：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span>[] array = &#123;<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>&#125;;</span><br></pre></td></tr></table></figure>



<p>知道了数组的数据起始地址 $BaseAddress$，就可以由公式 $BaseAddress +i* size$ 计算出索引元素的地址</p>
<ul>
<li>$i$即索引，在Java、C等语言都是从0开始</li>
<li>$size$ 是每个元素占用字节，例如 $int$ 占4，$double$ 占8</li>
</ul>
<h2 id="1-2-性能"><a href="#1-2-性能" class="headerlink" title="1.2 性能"></a>1.2 性能</h2><h3 id="1-2-1-空间占用"><a href="#1-2-1-空间占用" class="headerlink" title="1.2.1 空间占用"></a>1.2.1 空间占用</h3><p>Java 中数组结构为</p>
<ul>
<li>8字节 markword</li>
<li>4 字节 class 指针 (压缩 class 指针的情况)</li>
<li>4字节数组大小(决定了数组最大容量是$2^{32}$)</li>
<li>数组元素 + 对齐字节 (Java 中所有对象大小都是 8 字节的整数倍 ^12，不足的要用对齐字节补足)</li>
</ul>
<p>例如</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span>[] array = &#123;<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>&#125;;</span><br></pre></td></tr></table></figure>

<p>的大小为 40 个字节，组成如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">8 + 4 + 4 + 5*4 + 4(alignment)</span><br></pre></td></tr></table></figure>

<h3 id="1-2-2-随机访问"><a href="#1-2-2-随机访问" class="headerlink" title="1.2.2 随机访问"></a>1.2.2 随机访问</h3><p>即根据索引查找元素，时间复杂度是 $O(1)$  </p>
<h1 id="2-二维数组"><a href="#2-二维数组" class="headerlink" title="2. 二维数组"></a>2. 二维数组</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span>[][] array = &#123;</span><br><span class="line">	&#123;<span class="number">11</span>, <span class="number">12</span>, <span class="number">13</span>, <span class="number">14</span>, <span class="number">15</span>&#125;,</span><br><span class="line">	&#123;<span class="number">21</span>, <span class="number">22</span>, <span class="number">23</span>, <span class="number">24</span>, <span class="number">25</span>&#125;,</span><br><span class="line">	&#123;<span class="number">31</span>, <span class="number">32</span>, <span class="number">33</span>, <span class="number">34</span>, <span class="number">35</span>&#125;,</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>内存图如下：</p>
<img src="https://csh-picture.oss-cn-shenzhen.aliyuncs.com/img202309211006158.png" alt="image-20230912212740535" style="zoom:80%;" />

<ul>
<li>二维数组占 32 个字节，其中 array[0]，array[1]，array[2]三个元素分别保存了指向三个一维数组的引用</li>
<li>三个一维数组各占40个字节</li>
<li>它们在内层布局上是连续的</li>
</ul>
<h2 id="2-1-局部性原理"><a href="#2-1-局部性原理" class="headerlink" title="2.1 局部性原理"></a>2.1 局部性原理</h2><p>只讨论空间局部性</p>
<ul>
<li>CPU 读取内存(速度慢) 数据后，会将其放入高速缓存 (速度快)当中，如果后来的计算再用到此数据4在缓存中能读到的话，就不必读内存了</li>
<li>缓存的最小存储单位是缓存行 (cache line) ，一般是 64 bytes，一次读的数据少了不划算啊，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其<strong>临近的数据</strong>，这就是所谓<strong>空间局部性</strong></li>
</ul>
<h1 id="3-链表"><a href="#3-链表" class="headerlink" title="3. 链表"></a>3. 链表</h1><p>在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续</p>
<h2 id="3-1-分类"><a href="#3-1-分类" class="headerlink" title="3.1 分类"></a>3.1 分类</h2><h3 id="3-1-1-单向链表"><a href="#3-1-1-单向链表" class="headerlink" title="3.1.1 单向链表"></a>3.1.1 单向链表</h3><p>特点：每个元素只知道自己的下一个元素是谁</p>
<p><img src="https://csh-picture.oss-cn-shenzhen.aliyuncs.com/img202309211006118.png" alt="image-20230913215216933"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">Node</span> &#123;</span><br><span class="line">        <span class="type">int</span> value;  <span class="comment">// 值</span></span><br><span class="line">        Node next;  <span class="comment">// 下一个节点指针</span></span><br><span class="line"></span><br><span class="line">        <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(<span class="type">int</span> value, Node next)</span> &#123;</span><br><span class="line">            <span class="built_in">this</span>.value = value;</span><br><span class="line">            <span class="built_in">this</span>.next = next;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="3-1-2-双向链表"><a href="#3-1-2-双向链表" class="headerlink" title="3.1.2 双向链表"></a>3.1.2 双向链表</h3><p>特点：每个元素知道其上一个元素和下一个元素</p>
<p><img src="https://csh-picture.oss-cn-shenzhen.aliyuncs.com/img202309211006154.png" alt="image-20230913215435146"></p>
<h3 id="3-1-3-循环链表"><a href="#3-1-3-循环链表" class="headerlink" title="3.1.3 循环链表"></a>3.1.3 循环链表</h3><p>特点：通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head</p>
<p><img src="https://csh-picture.oss-cn-shenzhen.aliyuncs.com/img202309211006167.png" alt="image-20230913215501839"></p>
<p>链表内还有一种特殊的节点称为哨兵 (Sentinel) 节点，也叫做哑元(Dummy) 节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示</p>
<p><img src="https://csh-picture.oss-cn-shenzhen.aliyuncs.com/img202309211006201.png" alt="image-20230913215643513"></p>
<h2 id="3-2-性能"><a href="#3-2-性能" class="headerlink" title="3.2 性能"></a>3.2 性能</h2><h3 id="3-2-1-随机性能"><a href="#3-2-1-随机性能" class="headerlink" title="3.2.1 随机性能"></a>3.2.1 随机性能</h3><p>根据 index 查找，时间复杂度 $O(n)$    </p>
<h3 id="3-2-2-插入或删除"><a href="#3-2-2-插入或删除" class="headerlink" title="3.2.2 插入或删除"></a>3.2.2 插入或删除</h3><p>起始位置：$O(1)$ </p>
<p>结束位置：如果已知 tail 尾节点是 $O(1)$，不知道 tail 尾节点是 $O(n)$</p>
<p>中间位置：根据 index 查找时间$ + O(1)$   </p>

    </div>

    
    <div class="about">
        <h1>About this Post</h1>
        <div class="details">
            <p>This post is written by John Doe, licensed under <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc/4.0">CC BY-NC 4.0</a>.</p>
        </div>
        
        <p class="tags text-capitalize">
            
            <i class="icon"></i>
            <a href="/tags/Algorithm/" class="tag">#Algorithm</a>
        </p>
        
    </div>
    

    <div class="container post-prev-next">
        
        <a href="/2023/09/21/day01-MySQL%E5%9F%BA%E7%A1%80/" class="next">
            <div>
                <div class="text">
                    <p class="label">Next</p>
                    <h3 class="title">day01-MySQL基础</h3>
                </div>
            </div>
        </a>
        
        
        <a href="/2023/09/21/Linux%E5%B8%B8%E7%94%A8%E5%91%BD%E4%BB%A4/" class="prev">
            <div>
                <div class="text">
                    <p class="label">Previous</p>
                    <h3 class="title">Linux常用命令</>
                </div>
            </div>
        </a>
        
    </div>

    
        
        
    
</article>

        <footer>
    <div class="inner">
        <div class="links">
            
            <div class="group">
                <h2 class="title">Blog</h2>
                
                <a href="/" class="item">Blog</a>
                
                <a href="/archives" class="item">Archives</a>
                
                <a href="/tags" class="item">Tags</a>
                
                <a href="/categories" class="item">Categories</a>
                
                <a href="/about" class="item">About</a>
                
            </div>
            
            <div class="group">
                <h2 class="title">Projects</h2>
                
                <a target="_blank" rel="noopener" href="https://github.com/MrWillCom/rsa-cli" class="item">RSA CLI</a>
                
                <a target="_blank" rel="noopener" href="https://github.com/MrWillCom/hexo-theme-cupertino" class="item">Hexo Theme Cupertino</a>
                
                <a target="_blank" rel="noopener" href="https://github.com/MrWillCom/a-calendar" class="item">A Calendar</a>
                
                <a target="_blank" rel="noopener" href="https://github.com/MrWillCom/auto-mirroring-bucket" class="item">Auto Mirroring Bucket</a>
                
            </div>
            
            <div class="group">
                <h2 class="title">Me</h2>
                
                <a target="_blank" rel="noopener" href="https://github.com/Satellite2426" class="item">GitHub</a>
                
                <a href="mailto:chaoshihan2426@gmail.com" class="item">Email</a>
                
            </div>
            
        </div>
        <span>&copy; 2023 John Doe<br>Powered by <a href="http://hexo.io/" target="_blank">Hexo</a> </span>
        
        
            <br>
            <div class="color-scheme-toggle" role="radiogroup" id="theme-color-scheme-toggle">
                <label>
                    <input type="radio" value="light">
                    <span>Light</span>
                </label>
                <label>
                    <input type="radio" value="dark">
                    <span>Dark</span>
                </label>
                <label>
                    <input type="radio" value="auto">
                    <span>Auto</span>
                </label>
            </div>
        
    </div>
</footer>


        
<script src="/js/main.js"></script>

        
        
        

        
        <script src="https://unpkg.com/scrollreveal"></script>
        <script>
            window.addEventListener('load', () => {
                ScrollReveal({ delay: 250, reset: true, easing: 'cubic-bezier(0, 0, 0, 1)' })
                ScrollReveal().reveal('.post-list-item .cover-img img')
                ScrollReveal().reveal('.post-list-item, .card, .content p img, .content .block-large img', { distance: '60px', origin: 'bottom', duration: 800 })
            })
        </script>
        
    </body>
</html>